#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int kMaxN = 1e5 + 10;
const int kInf = 1e9;

vector<pair<int, int>> g[kMaxN];
int dist[kMaxN];

void Dijkstra(int n, int s) {
  priority_queue<pair<int, int>> pq;

  fill(dist, dist + n, kInf);
  dist[s] = 0;
  pq.emplace(-dist[s], s);
  while (!pq.empty()) {
    int d = -pq.top().first, u = pq.top().second;

    pq.pop();
    if (dist[u] != d) {
      continue;
    }
    for (const pair<int, int>& edge : g[u]) {
      if (dist[edge.first] > d + edge.second) {
        dist[edge.first] = d + edge.second;
        pq.emplace(-dist[edge.first], edge.first);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, m, s;

  cin >> n >> m >> s;
  s--;
  for (int i = 0; i < m; i++) {
    int u, v, w;

    cin >> u >> v >> w;
    u--;
    v--;
    g[u].emplace_back(v, w);
  }
  Dijkstra(n, s);
  for (int i = 0; i < n; i++) {
    cout << dist[i] << " ";
  }
  cout << "\n";
  return 0;
}